#pragma once

namespace stl
{
	template<typename T> class Trie;

	template<typename T>
	class TrieNode
	{
		typedef TrieNode<T> Node;
	public:
		TrieNode() : m_data(' '), m_flag(false), m_children(nullptr), m_size(0) {}

		~TrieNode() {
			if (m_children != nullptr) {
				for (int i = 0; i < m_size; i++) {
					delete m_children[i];
				}
				delete[] m_children;
				m_children = nullptr;
			}
		}

		void insert(int idx, Node *child) {
			auto children = new Node *[m_size + 1];
			for (int i = 0; i < idx; i++) {
				children[i] = m_children[i];
			}
			children[idx] = child;
			for (int i = idx; i < m_size; i++) {
				children[i + 1] = m_children[i];
			}
			if (m_children != nullptr) {
				delete[] m_children;
				m_children = nullptr;
			}
			m_children = children;
			m_size += 1;
		}

	private:
		friend class Trie<T>;
		char m_data;
		bool m_flag;
		Node **m_children;
		int m_size;
	};
}